<!DOCTYPE html>
            
<HTML>
<HEAD>
<meta name="booktitle" content="Developing Applications With Objective Caml" >
 <meta charset="ISO-8859-1"><meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0">
<META name="GENERATOR" content="hevea 1.05-7 of 2000-02-24">
<META NAME="Author" CONTENT="Christian.Queinnec@lip6.fr">
<LINK rel=stylesheet type="text/css" href="videoc-ocda.css">
<script language="JavaScript" src="videoc.js"><!--
//--></script>
<TITLE>
 Finding Least Cost Paths
</TITLE>
</HEAD>
<BODY class="regularBody">
<A HREF="book-ora124.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="index.html"><IMG SRC ="contents_motif.gif" ALT="Contents"></A>
<A HREF="book-ora127.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2> Finding Least Cost Paths</H2>
Many applications need to find least cost paths through weighted
directed graphs. The problem is to find a path through a graph in
which non-negative weights are associated with the arcs. We will use
Dijkstra's algorithm to determine the path.<BR>
<BR>
This will be an opportunity to use several previously introduced libraries.
In the order of appearance, the following modules will be used:
<TT>Genlex</TT> and <TT>Printf</TT> for input and output, the module
<TT>Weak</TT> to implement a cache, the module <TT>Sys</TT>
to track the time saved by a cache, and the <TT>Awi</TT> library to
construct a graphical user interface. The module <TT>Sys</TT> is also
used to construct a standalone application that takes the name of a
file describing the graph as a command line argument.<BR>
<BR>
<A NAME="toc174"></A>
<H3> Graph Representions</H3>
A weighted directed graph is defined by a set of nodes, a set of
edges, and a mapping from the set of edges to a set of values. There
are numerous implementations of the data type
<EM>weighted directed graph</EM>.
<UL>
<LI>
 adjacency matrices:<BR>each element (<I>m</I>(<I>i</I>,<I>j</I>)) of the matrix represents an edge from node <I>i</I>
to <I>j</I> and the value of the element is the weight of the edge;

<LI> adjacency lists:<BR>each node <I>i</I> is associated with a list [(<I>j</I><SUB><FONT SIZE=2>1</FONT></SUB>,<I>w</I><SUB><FONT SIZE=2>1</FONT></SUB>); ..; (<I>j</I><SUB><FONT SIZE=2><I>n</I></FONT></SUB>,<I>w</I><SUB><FONT SIZE=2><I>n</I></FONT></SUB>)] of nodes
and each triple (<I>i</I>, <I>j</I><SUB><FONT SIZE=2><I>k</I></FONT></SUB>, <I>w</I><SUB><FONT SIZE=2><I>k</I></FONT></SUB>) is an edge of the graph, with weight <I>w</I><SUB><FONT SIZE=2><I>k</I></FONT></SUB>;

<LI> a triple:<BR>a list of nodes, a list of edges and a function that computes the
weights of the edges.</UL>
The behavior of the representations depends on the size and the number
of edges in the graph. Since one goal of this application is to show
how to cache certain previously executed computations without using
all of memory, an adjacency matrix is used to represent weighted
directed graphs. In this way, memory usage will not be increased by
list manipulations.<BR>
<BR>


<PRE><BR># <B>type</B><CODE> </CODE><CODE> </CODE>cost<CODE> </CODE><CODE> </CODE><CODE>=</CODE><CODE> </CODE>Nan<CODE> </CODE><CODE>|</CODE><CODE> </CODE>Cost<CODE> </CODE><B>of</B><CODE> </CODE>float;;<BR># <B>type</B><CODE> </CODE><CODE> </CODE>adj_mat<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE> </CODE>cost<CODE> </CODE>array<CODE> </CODE>array;;<BR># <B>type</B><CODE> </CODE>'a<CODE> </CODE>graph<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE><B>mutable</B><CODE> </CODE>ind<CODE> </CODE><CODE>:</CODE><CODE> </CODE>int;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>size<CODE> </CODE><CODE>:</CODE><CODE> </CODE>int;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>nodes<CODE> </CODE><CODE>:</CODE><CODE> </CODE>'a<CODE> </CODE>array;<CODE> </CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>m<CODE> </CODE><CODE>:</CODE><CODE> </CODE>adj_mat};;<BR>

</PRE>

The field <TT>size</TT> indicates the maximal number of nodes, the field
<TT>ind</TT> the actual number of nodes. <BR>
<BR>
We define functions to let us create graphs edge by edge.
<BR>
<BR>
The function to create a graph takes as arguments a node
and the maximal number of nodes.


<PRE><BR># <B>let</B><CODE> </CODE>create_graph<CODE> </CODE>n<CODE> </CODE>s<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE>{<CODE> </CODE>ind<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>0</CODE>;<CODE> </CODE>size<CODE> </CODE><CODE>=</CODE><CODE> </CODE>s;<CODE> </CODE>nodes<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Array.create<CODE> </CODE>s<CODE> </CODE>n;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>m<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Array.create_matrix<CODE> </CODE>s<CODE> </CODE>s<CODE> </CODE>Nan<CODE> </CODE>}<CODE> </CODE>;;<BR><CODE>val create_graph : 'a -&gt; int -&gt; 'a graph = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
The function <TT>belongs_to</TT> checks if the node <TT>n</TT> is contained in the
graph <TT>g</TT>.


<PRE><BR># <B>let</B><CODE> </CODE>belongs_to<CODE> </CODE>n<CODE> </CODE>g<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>aux<CODE> </CODE>i<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><TT>(</TT>i<CODE> </CODE><CODE>&lt;</CODE><CODE> </CODE>g<CODE>.</CODE>size<TT>)</TT><CODE> </CODE><CODE>&amp;</CODE><CODE> </CODE><TT>(</TT><TT>(</TT>g<CODE>.</CODE>nodes<CODE>.</CODE><TT>(</TT>i<TT>)</TT><CODE> </CODE><CODE>=</CODE><CODE> </CODE>n<TT>)</TT><CODE> </CODE><B>or</B><CODE> </CODE><TT>(</TT>aux<CODE> </CODE><TT>(</TT>i<CODE>+</CODE><CODE>1</CODE><TT>)</TT><TT>)</TT><TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE>aux<CODE> </CODE><CODE>0</CODE>;;<BR><CODE>val belongs_to : 'a -&gt; 'a graph -&gt; bool = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
The function <TT>index</TT> returns the index of the node <TT>n</TT>
in the graph <TT>g</TT>. If the node does not exist, a
<TT>Not_found</TT> exception is thrown.


<PRE><BR># <B>let</B><CODE> </CODE>index<CODE> </CODE>n<CODE> </CODE>g<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>aux<CODE> </CODE>i<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>i<CODE> </CODE><CODE>&gt;=</CODE><CODE> </CODE>g<CODE>.</CODE>size<CODE> </CODE><B>then</B><CODE> </CODE>raise<CODE> </CODE>Not_found<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE><B>if</B><CODE> </CODE>g<CODE>.</CODE>nodes<CODE>.</CODE><TT>(</TT>i<TT>)</TT><CODE> </CODE><CODE>=</CODE><CODE> </CODE>n<CODE> </CODE><B>then</B><CODE> </CODE>i<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE>aux<CODE> </CODE><TT>(</TT>i<CODE>+</CODE><CODE>1</CODE><TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE>aux<CODE> </CODE><CODE>0</CODE><CODE> </CODE>;;<BR><CODE>val index : 'a -&gt; 'a graph -&gt; int = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
The next two functions are for adding nodes and edges of
cost <TT>c</TT> to graphs.


<PRE><BR># <B>let</B><CODE> </CODE>add_node<CODE> </CODE>n<CODE> </CODE>g<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>g<CODE>.</CODE>ind<CODE> </CODE><CODE>=</CODE><CODE> </CODE>g<CODE>.</CODE>size<CODE> </CODE><B>then</B><CODE> </CODE>failwith<CODE> </CODE><CODE>"the graph is full"</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE><B>if</B><CODE> </CODE>belongs_to<CODE> </CODE>n<CODE> </CODE>g<CODE> </CODE><B>then</B><CODE> </CODE>failwith<CODE> </CODE><CODE>"the node already exists"</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE><TT>(</TT>g<CODE>.</CODE>nodes<CODE>.</CODE><TT>(</TT>g<CODE>.</CODE>ind<TT>)</TT><CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>n;<CODE> </CODE>g<CODE>.</CODE>ind<CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>g<CODE>.</CODE>ind<CODE> </CODE><CODE>+</CODE><CODE> </CODE><CODE>1</CODE><TT>)</TT><CODE> </CODE>;;<BR><CODE>val add_node : 'a -&gt; 'a graph -&gt; unit = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE>add_edge<CODE> </CODE>e1<CODE> </CODE>e2<CODE> </CODE>c<CODE> </CODE>g<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>try</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>x<CODE> </CODE><CODE>=</CODE><CODE> </CODE>index<CODE> </CODE>e1<CODE> </CODE>g<CODE> </CODE><B>and</B><CODE> </CODE>y<CODE> </CODE><CODE>=</CODE><CODE> </CODE>index<CODE> </CODE>e2<CODE> </CODE>g<CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>g<CODE>.</CODE>m<CODE>.</CODE><TT>(</TT>x<TT>)</TT><CODE>.</CODE><TT>(</TT>y<TT>)</TT><CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>Cost<CODE> </CODE>c<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>with</B><CODE> </CODE>Not_found<CODE> </CODE>-&gt;<CODE> </CODE>failwith<CODE> </CODE><CODE>"node does not exist"</CODE><CODE> </CODE>;;<BR><CODE>val add_edge : 'a -&gt; 'a -&gt; float -&gt; 'a graph -&gt; unit = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
Now it is easy to create a complete weighted directed graph
starting with a list of nodes and edges. The function
<TT>test_aho</TT> constructs the graph of figure <A HREF="book-ora125.html#fig-aho">13.8</A>:


<PRE><BR># <B>let</B><CODE> </CODE>test_aho<CODE> </CODE>()<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>g<CODE> </CODE><CODE>=</CODE><CODE> </CODE>create_graph<CODE> </CODE><CODE>"nothing"</CODE><CODE> </CODE><CODE>5</CODE><CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>List.iter<CODE> </CODE><TT>(</TT><B>fun</B><CODE> </CODE>x<CODE> </CODE>-&gt;<CODE> </CODE>add_node<CODE> </CODE>x<CODE> </CODE>g<TT>)</TT><CODE> </CODE><CODE>[</CODE><CODE>"A"</CODE>;<CODE> </CODE><CODE>"B"</CODE>;<CODE> </CODE><CODE>"C"</CODE>;<CODE> </CODE><CODE>"D"</CODE>;<CODE> </CODE><CODE>"E"</CODE><CODE>]</CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>List.iter<CODE> </CODE><TT>(</TT><B>fun</B><CODE> </CODE><TT>(</TT>a<CODE>,</CODE>b<CODE>,</CODE>c<TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE>add_edge<CODE> </CODE>a<CODE> </CODE>b<CODE> </CODE>c<CODE> </CODE>g<TT>)</TT><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>[</CODE><CODE>"A"</CODE><CODE>,</CODE><CODE>"B"</CODE><CODE>,</CODE><CODE>1</CODE><CODE>0</CODE><CODE>.</CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>"A"</CODE><CODE>,</CODE><CODE>"D"</CODE><CODE>,</CODE><CODE>3</CODE><CODE>0</CODE><CODE>.</CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>"A"</CODE><CODE>,</CODE><CODE>"E"</CODE><CODE>,</CODE><CODE>1</CODE><CODE>0</CODE><CODE>0</CODE><CODE>.</CODE><CODE>0</CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>"B"</CODE><CODE>,</CODE><CODE>"C"</CODE><CODE>,</CODE><CODE>5</CODE><CODE>0</CODE><CODE>.</CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>"C"</CODE><CODE>,</CODE><CODE>"E"</CODE><CODE>,</CODE><CODE>1</CODE><CODE>0</CODE><CODE>.</CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>"D"</CODE><CODE>,</CODE><CODE>"C"</CODE><CODE>,</CODE><CODE>2</CODE><CODE>0</CODE><CODE>.</CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>"D"</CODE><CODE>,</CODE><CODE>"E"</CODE><CODE>,</CODE><CODE>6</CODE><CODE>0</CODE><CODE>.]</CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>for</B><CODE> </CODE>i<CODE>=</CODE><CODE>0</CODE><CODE> </CODE><B>to</B><CODE> </CODE>g<CODE>.</CODE>ind<CODE> </CODE><CODE>-</CODE><CODE>1</CODE><CODE> </CODE><B>do</B><CODE> </CODE>g<CODE>.</CODE>m<CODE>.</CODE><TT>(</TT>i<TT>)</TT><CODE>.</CODE><TT>(</TT>i<TT>)</TT><CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>Cost<CODE> </CODE><CODE>0</CODE><CODE>.</CODE><CODE>0</CODE><CODE> </CODE><B>done</B>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>g;;<BR><CODE>val test_aho : unit -&gt; string graph = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE>a<CODE> </CODE><CODE>=</CODE><CODE> </CODE>test_aho();;<BR><CODE>val a : string graph =</CODE><BR><CODE>  {ind=5; size=5; nodes=[|"A"; "B"; "C"; "D"; "E"|];</CODE><BR><CODE>   m=[|[|Cost 0; Cost 10; Nan; Cost 30; Cost ...|]; ...|]}</CODE><BR>

</PRE>
<BR>
<BR>
<BLOCKQUOTE><DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV>
<DIV ALIGN=center>
<IMG SRC="book-ora055.gif">
</DIV>
<BR>
<DIV ALIGN=center>Figure 13.8: The test graph</DIV><BR>

<A NAME="fig-aho"></A>
<DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
<H4> Constructing Graphs</H4>It is tedious to directly construct graphs in a program. To avoid
this, we define a concise textual representation for graphs. We can
define the graphs in text files and construct them in applications by
reading the text files.<BR>
<BR>
The textual representation for a graph consists of lines of
the following forms:
<UL>
<LI>
 the number of nodes: <TT>SIZE number</TT>;

<LI> the name of a node: <TT>NODE name</TT>;

<LI> the cost of an edge: <TT>EDGE name1 name2 cost</TT>;

<LI> a comment: <TT>#</TT><TT> comment</TT>.
</UL>
For example, the following file, <TT>aho.dat</TT>, describes the graph of 
figure <A HREF="book-ora125.html#fig-aho">13.8</A>&nbsp;:
<PRE>
SIZE 5
NODE A
NODE B
NODE C
NODE D
NODE E
EDGE A B 10.0
EDGE A D 30.0
EDGE A E 100.0
EDGE B C 50.
EDGE C E 10.
EDGE D C 20.
EDGE D E 60.
</PRE>To read graph files, we use the lexical analysis module <TT>Genlex</TT>.
The lexical analyser is constructed from a list of keywords
<TT>keywords</TT>. <BR>
<BR>
The function
<TT>parse_line</TT> executes the actions associated to the key words
by modifying the reference to a graph.


<PRE><BR># <B>let</B><CODE> </CODE>keywords<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>[</CODE><CODE> </CODE><CODE>"SIZE"</CODE>;<CODE> </CODE><CODE>"NODE"</CODE>;<CODE> </CODE><CODE>"EDGE"</CODE>;<CODE> </CODE><CODE>"#"</CODE><CODE>]</CODE>;;<BR><CODE>val keywords : string list = ["SIZE"; "NODE"; "EDGE"; "#"]</CODE><BR># <B>let</B><CODE> </CODE>lex_line<CODE> </CODE>l<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Genlex.make_lexer<CODE> </CODE>keywords<CODE> </CODE><TT>(</TT>Stream.of_string<CODE> </CODE>l<TT>)</TT>;;<BR><CODE>val lex_line : string -&gt; Genlex.token Stream.t = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE>parse_line<CODE> </CODE>g<CODE> </CODE>s<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE><CODE> </CODE>s<CODE> </CODE><B>with</B><CODE> </CODE><B>parser</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>[&lt;</CODE><CODE> </CODE><CODE>'</CODE><TT>(</TT>Genlex<CODE>.</CODE>Kwd<CODE> </CODE><CODE> </CODE><CODE>"SIZE"</CODE><TT>)</TT>;<CODE> </CODE><CODE>'</CODE><TT>(</TT>Genlex<CODE>.</CODE>Int<CODE> </CODE>n<TT>)</TT><CODE> </CODE><CODE>&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>g<CODE> </CODE><CODE>:=</CODE><CODE> </CODE>create_graph<CODE> </CODE><CODE>""</CODE><CODE> </CODE>n<BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>[&lt;</CODE><CODE> </CODE><CODE>'</CODE><TT>(</TT>Genlex<CODE>.</CODE>Kwd<CODE> </CODE><CODE> </CODE><CODE>"NODE"</CODE><TT>)</TT>;<CODE> </CODE><CODE>'</CODE><TT>(</TT>Genlex<CODE>.</CODE>Ident<CODE> </CODE>name<TT>)</TT><CODE> </CODE><CODE>&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>add_node<CODE> </CODE>name<CODE> </CODE><CODE>!</CODE>g<BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>[&lt;</CODE><CODE> </CODE><CODE>'</CODE><TT>(</TT>Genlex<CODE>.</CODE>Kwd<CODE> </CODE><CODE> </CODE><CODE>"EDGE"</CODE><TT>)</TT>;<CODE> </CODE><CODE>'</CODE><TT>(</TT>Genlex<CODE>.</CODE>Ident<CODE> </CODE>e1<TT>)</TT>;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>'</CODE><TT>(</TT>Genlex<CODE>.</CODE>Ident<CODE> </CODE><CODE> </CODE>e2<TT>)</TT>;<CODE> </CODE><CODE>'</CODE><TT>(</TT>Genlex<CODE>.</CODE>Float<CODE> </CODE>c<TT>)</TT><CODE> </CODE><CODE>&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>add_edge<CODE> </CODE>e1<CODE> </CODE>e2<CODE> </CODE>c<CODE> </CODE><CODE>!</CODE>g<BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>[&lt;</CODE><CODE> </CODE><CODE>'</CODE><TT>(</TT>Genlex<CODE>.</CODE>Kwd<CODE> </CODE><CODE> </CODE><CODE>"#"</CODE><TT>)</TT><CODE> </CODE><CODE>&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE>()<BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>[&lt;&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE>()<CODE> </CODE>;;<BR><CODE>val parse_line : string graph ref -&gt; Genlex.token Stream.t -&gt; unit = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
The analyzer is used to define the function creating a graph
from the description in the file:


<PRE><BR># <B>let</B><CODE> </CODE>create_graph<CODE> </CODE>name<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>g<CODE> </CODE><CODE>=</CODE><CODE> </CODE>ref<CODE> </CODE>{ind<CODE>=</CODE><CODE>0</CODE>;<CODE> </CODE>size<CODE>=</CODE><CODE>0</CODE>;<CODE> </CODE>nodes<CODE> </CODE><CODE>=[||]</CODE>;<CODE> </CODE>m<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>[||]}</CODE><CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>ic<CODE> </CODE><CODE>=</CODE><CODE> </CODE>open_in<CODE> </CODE>name<CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>try</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>print_string<CODE> </CODE><TT>(</TT><CODE>"Loading "</CODE><CODE>^</CODE>name<CODE>^</CODE><CODE>": "</CODE><TT>)</TT>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>while</B><CODE> </CODE><B>true</B><CODE> </CODE><B>do</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>print_string<CODE> </CODE><CODE>"."</CODE>;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>l<CODE> </CODE><CODE>=</CODE><CODE> </CODE>input_line<CODE> </CODE>ic<CODE> </CODE><B>in</B><CODE> </CODE>parse_line<CODE> </CODE>g<CODE> </CODE><TT>(</TT>lex_line<CODE> </CODE>l<TT>)</TT><CODE> </CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>done</B>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>!</CODE>g<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>with</B><CODE> </CODE>End_of_file<CODE> </CODE>-&gt;<CODE> </CODE>print_newline();<CODE> </CODE>close_in<CODE> </CODE>ic;<CODE> </CODE><CODE>!</CODE>g<CODE> </CODE>;;<BR><CODE>val create_graph : string -&gt; string graph = &lt;fun&gt;</CODE><BR>

</PRE>

The following command constructs a graph from the file <TT>aho.dat</TT>.


<PRE><BR># <B>let</B><CODE> </CODE>b<CODE> </CODE><CODE>=</CODE><CODE> </CODE>create_graph<CODE> </CODE><CODE>"PROGRAMMES/aho.dat"</CODE><CODE> </CODE>;;<BR><CODE>Loading PROGRAMMES/aho.dat: ..............</CODE><BR><CODE>val b : string graph =</CODE><BR><CODE>  {ind=5; size=5; nodes=[|"A"; "B"; "C"; "D"; "E"|];</CODE><BR><CODE>   m=[|[|Nan; Cost 10; Nan; Cost 30; Cost 100|]; ...|]}</CODE><BR>

</PRE>
<BR>
<BR>
<A NAME="toc175"></A>
<H3> Dijkstra's Algorithm</H3>
Dijkstra's algorithm finds a least cost path between two nodes. The
cost of a path between node <I>n</I>1 and node <I>n</I>2 is the sum of the costs
of the edges on that path. The algorithm requires that costs
always be positive, so there is no benefit in passing through a node more than
once.<BR>
<BR>
Dijkstra's algorithm effectively computes the minimal cost paths
of all nodes of the graph which can be reached from a source node <I>n</I>1.
The idea is to consider a set containing only nodes of which the least
cost path to <I>n</I>1 is already known. This set is enlarged
successively, considering nodes which can be accessed directly by an edge
from one of the nodes already contained in the set. From these candidates,
the one with the best cost path to the source node is added to the set.<BR>
<BR>
To keep track of the state of the computation, the type 
<I>comp_state</I> is defined, as well as a function for creating an
initial state:


<PRE><BR># <B>type</B><CODE> </CODE>comp_state<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE>paths<CODE> </CODE><CODE>:</CODE><CODE> </CODE>int<CODE> </CODE>array;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>already_treated<CODE> </CODE><CODE>:</CODE><CODE> </CODE>bool<CODE> </CODE>array;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>distances<CODE> </CODE><CODE>:</CODE><CODE> </CODE>cost<CODE> </CODE>array;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>source<CODE> </CODE><CODE>:</CODE><CODE> </CODE>int;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>nn<CODE> </CODE><CODE>:</CODE><CODE> </CODE>int};;<BR># <B>let</B><CODE> </CODE>create_state<CODE> </CODE>()<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE> </CODE>{<CODE> </CODE>paths<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>[||]</CODE>;<CODE> </CODE>already_treated<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>[||]</CODE>;<CODE> </CODE>distances<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>[||]</CODE>;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>nn<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>0</CODE>;<CODE> </CODE>source<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>0</CODE>};;<BR>

</PRE>

The field <TT>source</TT> contains the start node.
The field <TT>already_treated</TT> indicates the nodes whose optimal
path from the source is already known. The field <TT>nn</TT> indicates the
total number of the graph's nodes.
The vector <TT>distances</TT> holds the minimal distances
between the source and the other nodes. For each node, the vector
<TT>path</TT> contains the preceding node on the least cost
path. The path to the source can be reconstructed from each node by using <TT>path</TT>.<BR>
<BR>

<H4> Cost Functions</H4>
Four functions on costs are defined:
<TT>a_cost</TT> to test for the existence of an edge,
<TT>float_of_cost</TT> to return the floating point value, 
<TT>add_cost</TT> to add two costs and
<TT>less_cost</TT> to check if one cost is smaller than another. <BR>
<BR>


<PRE><BR># <B>let</B><CODE> </CODE>a_cost<CODE> </CODE>c<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>c<CODE> </CODE><B>with</B><CODE> </CODE>Nan<CODE> </CODE>-&gt;<CODE> </CODE><B>false</B><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>_-&gt;</CODE><CODE> </CODE><B>true</B>;;<BR><CODE>val a_cost : cost -&gt; bool = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE>float_of_cost<CODE> </CODE>c<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>c<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE>Nan<CODE> </CODE>-&gt;<CODE> </CODE>failwith<CODE> </CODE><CODE>"float_of_cost"</CODE><BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Cost<CODE> </CODE>x<CODE> </CODE>-&gt;<CODE> </CODE>x;;<BR><CODE>val float_of_cost : cost -&gt; float = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE>add_cost<CODE> </CODE><CODE> </CODE>c1<CODE> </CODE>c2<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE><TT>(</TT>c1<CODE>,</CODE>c2<TT>)</TT><CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE>Cost<CODE> </CODE>x<CODE>,</CODE><CODE> </CODE>Cost<CODE> </CODE>y<CODE> </CODE>-&gt;<CODE> </CODE>Cost<CODE> </CODE><TT>(</TT>x<CODE>+.</CODE>y<TT>)</TT><BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Nan<CODE>,</CODE><CODE> </CODE>Cost<CODE> </CODE>y<CODE> </CODE>-&gt;<CODE> </CODE>c2<BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Cost<CODE> </CODE>x<CODE>,</CODE><CODE> </CODE>Nan<CODE> </CODE>-&gt;<CODE> </CODE>c1<CODE> </CODE><BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Nan<CODE>,</CODE><CODE> </CODE>Nan<CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE>c1;;<BR><CODE>val add_cost : cost -&gt; cost -&gt; cost = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE>less_cost<CODE> </CODE><CODE> </CODE>c1<CODE> </CODE>c2<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE><TT>(</TT>c1<CODE>,</CODE>c2<TT>)</TT><CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE>Cost<CODE> </CODE>x<CODE>,</CODE><CODE> </CODE>Cost<CODE> </CODE>y<CODE> </CODE>-&gt;<CODE> </CODE>x<CODE> </CODE><CODE>&lt;</CODE><CODE> </CODE>y<BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Cost<CODE> </CODE>x<CODE>,</CODE><CODE> </CODE>Nan<CODE> </CODE>-&gt;<CODE> </CODE><B>true</B><BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>_,</CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE><B>false</B>;;<BR><CODE>val less_cost : cost -&gt; cost -&gt; bool = &lt;fun&gt;</CODE><BR>

</PRE>

The value <TT>Nan</TT> plays a special role in the computations and in the
comparison. We will come back to this when we have presented the main
function (page <A HREF="book-ora125.html#fun-dij">??</A>).<BR>
<BR>

<H4> Implementing the Algorithm</H4>
The search for the next node with known least cost path is divided into
two functions. The first,
<TT>first_not_treated</TT>, selects the first node not already
contained in the set of nodes with known least cost paths. This node
serves as the initial value for the second function,
<TT>least_not_treated</TT>, which returns a node not already in the
set with a best cost path to the source. This path will be added to
the set.


<PRE><BR># <B>exception</B><CODE> </CODE>Found<CODE> </CODE><B>of</B><CODE> </CODE>int;;<BR><CODE>exception Found of int</CODE><BR># <B>let</B><CODE> </CODE>first_not_treated<CODE> </CODE>cs<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>try</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>for</B><CODE> </CODE>i<CODE>=</CODE><CODE>0</CODE><CODE> </CODE><B>to</B><CODE> </CODE>cs<CODE>.</CODE>nn<CODE>-</CODE><CODE>1</CODE><CODE> </CODE><B>do</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>not<CODE> </CODE>cs<CODE>.</CODE>already_treated<CODE>.</CODE><TT>(</TT>i<TT>)</TT><CODE> </CODE><B>then</B><CODE> </CODE>raise<CODE> </CODE><TT>(</TT>Found<CODE> </CODE>i<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>done</B>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>raise<CODE> </CODE>Not_found;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>0</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>with</B><CODE> </CODE>Found<CODE> </CODE>i<CODE> </CODE>-&gt;<CODE> </CODE>i<CODE> </CODE>;;<BR><CODE>val first_not_treated : comp_state -&gt; int = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE>least_not_treated<CODE> </CODE>p<CODE> </CODE>cs<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>ni<CODE> </CODE><CODE>=</CODE><CODE> </CODE>ref<CODE> </CODE>p<CODE> </CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>and</B><CODE> </CODE>nd<CODE> </CODE><CODE>=</CODE><CODE> </CODE>ref<CODE> </CODE>cs<CODE>.</CODE>distances<CODE>.</CODE><TT>(</TT>p<TT>)</TT><CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>for</B><CODE> </CODE>i<CODE>=</CODE>p<CODE>+</CODE><CODE>1</CODE><CODE> </CODE><B>to</B><CODE> </CODE>cs<CODE>.</CODE>nn<CODE>-</CODE><CODE>1</CODE><CODE> </CODE><B>do</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>not<CODE> </CODE>cs<CODE>.</CODE>already_treated<CODE>.</CODE><TT>(</TT>i<TT>)</TT><CODE> </CODE><B>then</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>less_cost<CODE> </CODE>cs<CODE>.</CODE>distances<CODE>.</CODE><TT>(</TT>i<TT>)</TT><CODE> </CODE><CODE> </CODE><CODE>!</CODE>nd<CODE> </CODE><B>then</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><TT>(</TT><CODE> </CODE>nd<CODE> </CODE><CODE>:=</CODE><CODE> </CODE>cs<CODE>.</CODE>distances<CODE>.</CODE><TT>(</TT>i<TT>)</TT>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>ni<CODE> </CODE><CODE>:=</CODE><CODE> </CODE>i<CODE> </CODE><TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>done</B>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>!</CODE>ni<CODE>,!</CODE>nd;;<BR><CODE>val least_not_treated : int -&gt; comp_state -&gt; int * cost = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
The function <TT>one_round</TT> selects a new node, adds it to the set of
treated nodes and computes the distances for any next candidates.


<PRE><BR># <B>exception</B><CODE> </CODE>No_way;;<BR><CODE>exception No_way</CODE><BR># <B>let</B><CODE> </CODE>one_round<CODE> </CODE>cs<CODE> </CODE><CODE> </CODE>g<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>p<CODE> </CODE><CODE>=</CODE><CODE> </CODE>first_not_treated<CODE> </CODE>cs<CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>np<CODE>,</CODE>nc<CODE> </CODE><CODE>=</CODE><CODE> </CODE>least_not_treated<CODE> </CODE>p<CODE> </CODE>cs<CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>not<TT>(</TT>a_cost<CODE> </CODE>nc<CODE> </CODE><CODE> </CODE><TT>)</TT><CODE> </CODE><B>then</B><CODE> </CODE>raise<CODE> </CODE>No_way<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>begin</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>cs<CODE>.</CODE>already_treated<CODE>.</CODE><TT>(</TT>np<TT>)</TT><CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE><B>true</B>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>for</B><CODE> </CODE>i<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>0</CODE><CODE> </CODE><B>to</B><CODE> </CODE>cs<CODE>.</CODE>nn<CODE> </CODE><CODE>-</CODE><CODE>1</CODE><CODE> </CODE><B>do</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>not<CODE> </CODE>cs<CODE>.</CODE>already_treated<CODE>.</CODE><TT>(</TT>i<TT>)</TT><CODE> </CODE><B>then</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>a_cost<CODE> </CODE>g<CODE>.</CODE>m<CODE>.</CODE><TT>(</TT>np<TT>)</TT><CODE>.</CODE><TT>(</TT>i<TT>)</TT><CODE> </CODE><B>then</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>ic<CODE> </CODE><CODE>=</CODE><CODE> </CODE>add_cost<CODE> </CODE>cs<CODE>.</CODE>distances<CODE>.</CODE><TT>(</TT>np<TT>)</TT><CODE> </CODE><CODE> </CODE>g<CODE>.</CODE>m<CODE>.</CODE><TT>(</TT>np<TT>)</TT><CODE>.</CODE><TT>(</TT>i<TT>)</TT><CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>less_cost<CODE> </CODE>ic<CODE> </CODE>cs<CODE>.</CODE>distances<CODE>.</CODE><TT>(</TT>i<TT>)</TT><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>then</B><CODE> </CODE><TT>(</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>cs<CODE>.</CODE>paths<CODE>.</CODE><TT>(</TT>i<TT>)</TT><CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>np;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>cs<CODE>.</CODE>distances<CODE>.</CODE><TT>(</TT>i<TT>)</TT><CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>ic<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><TT>)</TT><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>done</B>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>cs<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>end</B>;;<BR><CODE>val one_round : comp_state -&gt; 'a graph -&gt; comp_state = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
The only thing left in the implementation of Dijkstra's algorithm
is to iterate the preceding function. The function <TT>dij</TT> takes a node
and a graph as arguments and returns a value of type <TT>comp_state</TT>,
with the information from which the least cost paths from the source
to all the reachable nodes of the graph can be deduced.
<A NAME="fun-dij"></A>


<PRE><BR># <B>let</B><CODE> </CODE>dij<CODE> </CODE>s<CODE> </CODE>g<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>belongs_to<CODE> </CODE>s<CODE> </CODE>g<CODE> </CODE><B>then</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>begin</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>i<CODE> </CODE><CODE>=</CODE><CODE> </CODE>index<CODE> </CODE>s<CODE> </CODE>g<CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>cs<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE>paths<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Array.create<CODE> </CODE>g<CODE>.</CODE>ind<CODE> </CODE><TT>(</TT><CODE>-</CODE><CODE>1</CODE><TT>)</TT><CODE> </CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>already_treated<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Array.create<CODE> </CODE>g<CODE>.</CODE>ind<CODE> </CODE><B>false</B>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>distances<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Array.create<CODE> </CODE>g<CODE>.</CODE>ind<CODE> </CODE>Nan;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>nn<CODE> </CODE><CODE>=</CODE><CODE> </CODE>g<CODE>.</CODE>ind;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>source<CODE> </CODE><CODE>=</CODE><CODE> </CODE>i}<CODE> </CODE><CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>cs<CODE>.</CODE>already_treated<CODE>.</CODE><TT>(</TT>i<TT>)</TT><CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE><B>true</B>;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>for</B><CODE> </CODE>j<CODE>=</CODE><CODE>0</CODE><CODE> </CODE><B>to</B><CODE> </CODE>g<CODE>.</CODE>ind<CODE>-</CODE><CODE>1</CODE><CODE> </CODE><B>do</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>c<CODE> </CODE><CODE>=</CODE><CODE> </CODE>g<CODE>.</CODE>m<CODE>.</CODE><TT>(</TT>i<TT>)</TT><CODE>.</CODE><TT>(</TT>j<TT>)</TT><CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>cs<CODE>.</CODE>distances<CODE>.</CODE><TT>(</TT>j<TT>)</TT><CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>c;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>a_cost<CODE> </CODE>c<CODE> </CODE><B>then</B><CODE> </CODE>cs<CODE>.</CODE>paths<CODE>.</CODE><TT>(</TT>j<TT>)</TT><CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>i<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>done</B>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>try</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>for</B><CODE> </CODE>k<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>0</CODE><CODE> </CODE><B>to</B><CODE> </CODE>cs<CODE>.</CODE>nn<CODE>-</CODE><CODE>2</CODE><CODE> </CODE><B>do</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>ignore<TT>(</TT>one_round<CODE> </CODE>cs<CODE> </CODE>g<TT>)</TT><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>done</B>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>cs<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>with</B><CODE> </CODE>No_way<CODE> </CODE>-&gt;<CODE> </CODE>cs<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>end</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE>failwith<CODE> </CODE><CODE>"dij: node unknown"</CODE>;;<BR><CODE>val dij : 'a -&gt; 'a graph -&gt; comp_state = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
<TT>Nan</TT> is the initial value of the distances.
It represents an infinite distance, which conforms to the comparison
function <TT>less_cost</TT>. In contrast, for the addition of costs
(function <TT>add_cost</TT>), this value is treated as a zero.
This allows a simple implementation of the table of distances.<BR>
<BR>
Now the search with Dijkstra's algorithm can be tested.


<PRE><BR># <B>let</B><CODE> </CODE>g<CODE> </CODE><CODE>=</CODE><CODE> </CODE>test_aho<CODE> </CODE>();;<BR># <B>let</B><CODE> </CODE>r<CODE> </CODE><CODE>=</CODE><CODE> </CODE>dij<CODE> </CODE><CODE>"A"</CODE><CODE> </CODE>g;;<BR>

</PRE>
<BR>
<BR>
The return values are:


<PRE><BR># r<CODE>.</CODE>paths;;<BR><CODE>- : int array = [|0; 0; 3; 0; 2|]</CODE><BR># r<CODE>.</CODE>distances;;<BR><CODE>- : cost array = [|Cost 0; Cost 10; Cost 50; Cost 30; Cost 60|]</CODE><BR>

</PRE>
<BR>
<BR>

<H4> Displaying the Results</H4>
To make the results more readable, we now define a
display function.<BR>
<BR>
The table <TT>paths</TT> of the state returned by <TT>dij</TT>
only contains the last edges of the computed paths. 
In order to get the entire paths, it is necessary to recursively go
back to the source.


<PRE><BR># <B>let</B><CODE> </CODE>display_state<CODE> </CODE>f<CODE> </CODE><TT>(</TT>g<CODE>,</CODE>st<TT>)</TT><CODE> </CODE><CODE> </CODE>dest<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>belongs_to<CODE> </CODE>dest<CODE> </CODE>g<CODE> </CODE><B>then</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>d<CODE> </CODE><CODE>=</CODE><CODE> </CODE>index<CODE> </CODE>dest<CODE> </CODE>g<CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>aux<CODE> </CODE>is<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>is<CODE> </CODE><CODE>=</CODE><CODE> </CODE>st<CODE>.</CODE>source<CODE> </CODE><B>then</B><CODE> </CODE>Printf.printf<CODE> </CODE><CODE>"%a"</CODE><CODE> </CODE><CODE> </CODE>f<CODE> </CODE>g<CODE>.</CODE>nodes<CODE>.</CODE><TT>(</TT>is<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE><TT>(</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>old<CODE> </CODE><CODE>=</CODE><CODE> </CODE>st<CODE>.</CODE>paths<CODE>.</CODE><TT>(</TT>is<TT>)</TT><CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>aux<CODE> </CODE>old;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Printf.printf<CODE> </CODE><CODE>" -&gt; (%4.1f) %a"</CODE><CODE> </CODE><TT>(</TT>float_of_cost<CODE> </CODE>g<CODE>.</CODE>m<CODE>.</CODE><TT>(</TT>old<TT>)</TT><CODE>.</CODE><TT>(</TT>is<TT>)</TT><TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>f<CODE> </CODE>g<CODE>.</CODE>nodes<CODE>.</CODE><TT>(</TT>is<TT>)</TT><CODE> </CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>not<TT>(</TT>a_cost<CODE> </CODE>st<CODE>.</CODE>distances<CODE>.</CODE><TT>(</TT>d<TT>)</TT><TT>)</TT><CODE> </CODE><B>then</B><CODE> </CODE>Printf.printf<CODE> </CODE><CODE>"no way\n"</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE><TT>(</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>aux<CODE> </CODE>d;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Printf.printf<CODE> </CODE><CODE>" = %4.1f\n"</CODE><CODE> </CODE><TT>(</TT>float_of_cost<CODE> </CODE>st<CODE>.</CODE>distances<CODE>.</CODE><TT>(</TT>d<TT>)</TT><TT>)</TT><TT>)</TT>;;<BR><CODE>val display_state :</CODE><BR><CODE>  (out_channel -&gt; 'a -&gt; unit) -&gt; 'a graph * comp_state -&gt; 'a -&gt; unit = &lt;fun&gt;</CODE><BR>

</PRE>

This recursive function uses the command stack to display the nodes in the
right order. Note that the use of the format <TT>"a"</TT> requires the function parameter <TT>f</TT> to preserve the polymorphism of the graphs for the display.<BR>
<BR>
The optimal path between the nodes "A" (index 0) and "E" (index 4)
is displayed in the following way:


<PRE><BR># display_state<CODE> </CODE><TT>(</TT><B>fun</B><CODE> </CODE>x<CODE> </CODE>y<CODE> </CODE>-&gt;<CODE> </CODE>Printf.printf<CODE> </CODE><CODE>"%s!"</CODE><CODE> </CODE>y<TT>)</TT><CODE> </CODE><TT>(</TT>a<CODE>,</CODE>r<TT>)</TT><CODE> </CODE><CODE>"E"</CODE>;;<BR><CODE>A! -&gt; (30.0) D! -&gt; (20.0) C! -&gt; (10.0) E! = 60.0</CODE><BR><CODE>- : unit = ()</CODE><BR>

</PRE>
<BR>
<BR>
The different nodes of the path and the costs
of each route are shown.<BR>
<BR>
<A NAME="toc176"></A>
<H3> Introducing a Cache</H3>
Dijkstra's algorithm computes all least cost paths starting from a source.
The idea of preserving these least cost paths for the next inquiry with
the same source suggests itself. However, this storage could
occupy a considerable amount of memory. This suggests the use of
``weak pointers.'' If the results of a computation starting from a source
are stored in a table of weak pointers, it will be possible for the next
computation to check if the computation has already been done. Because the
pointers are weak, the memory occupied by the states can be freed
by the garbage collector if needed. This avoids interrupting the rest
of the program through the allocation of too much memory. In the worst case,
the computation has to be repeated for a future inquiry.<BR>
<BR>

<H4> Implementing a Cache</H4>
A new type <I>'a comp_graph</I> is defined:


<PRE><BR># <B>type</B><CODE> </CODE>'a<CODE> </CODE>comp_graph<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE>{<CODE> </CODE>g<CODE> </CODE><CODE>:</CODE><CODE> </CODE>'a<CODE> </CODE>graph;<CODE> </CODE>w<CODE> </CODE><CODE>:</CODE><CODE> </CODE>comp_state<CODE> </CODE>Weak.t<CODE> </CODE>}<CODE> </CODE>;;<BR>

</PRE>

The fields <TT>g</TT> and <TT>w</TT> correspond to the graph and to the table
of weak pointers, pointing to the computation states for each possible source.<BR>
<BR>
Such values are constructed by the function
<TT>create_comp_graph</TT>.


<PRE><BR># <B>let</B><CODE> </CODE>create_comp_graph<CODE> </CODE>g<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE>{<CODE> </CODE>g<CODE> </CODE><CODE>=</CODE><CODE> </CODE>g;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>w<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Weak.create<CODE> </CODE>g<CODE>.</CODE>ind<CODE> </CODE>}<CODE> </CODE>;;<BR><CODE>val create_comp_graph : 'a graph -&gt; 'a comp_graph = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
The function <TT>dij_quick</TT> checks to see if the computation has already been
done. If it has, the stored result is returned. Otherwise, the computation is
executed and the result is registered in the table of weak pointers.


<PRE><BR># <B>let</B><CODE> </CODE>dij_quick<CODE> </CODE>s<CODE> </CODE>cg<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>i<CODE> </CODE><CODE>=</CODE><CODE> </CODE>index<CODE> </CODE>s<CODE> </CODE>cg<CODE>.</CODE>g<CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>match</B><CODE> </CODE>Weak.get<CODE> </CODE>cg<CODE>.</CODE>w<CODE> </CODE>i<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>None<CODE> </CODE>-&gt;<CODE> </CODE><B>let</B><CODE> </CODE>cs<CODE> </CODE><CODE>=</CODE><CODE> </CODE>dij<CODE> </CODE>s<CODE> </CODE>cg<CODE>.</CODE>g<CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Weak.set<CODE> </CODE>cg<CODE>.</CODE>w<CODE> </CODE>i<CODE> </CODE><TT>(</TT>Some<CODE> </CODE>cs<TT>)</TT>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>cs<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Some<CODE> </CODE>cs<CODE> </CODE>-&gt;<CODE> </CODE>cs;;<BR><CODE>val dij_quick : 'a -&gt; 'a comp_graph -&gt; comp_state = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
The display function still can be used:


<PRE><BR># <B>let</B><CODE> </CODE>cg_a<CODE> </CODE><CODE>=</CODE><CODE> </CODE>create_comp_graph<CODE> </CODE>a<CODE> </CODE><B>in</B><BR><CODE> </CODE><B>let</B><CODE> </CODE>r<CODE> </CODE><CODE>=</CODE><CODE> </CODE>dij_quick<CODE> </CODE><CODE>"A"</CODE><CODE> </CODE>cg_a<CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE>display_state<CODE> </CODE><TT>(</TT><B>fun</B><CODE> </CODE>x<CODE> </CODE>y<CODE> </CODE>-&gt;<CODE> </CODE>Printf.printf<CODE> </CODE><CODE>"%s!"</CODE><CODE> </CODE>y<TT>)</TT><CODE> </CODE><TT>(</TT>a<CODE>,</CODE>r<TT>)</TT><CODE> </CODE><CODE>"E"</CODE><CODE> </CODE>;;<BR><CODE>A! -&gt; (30.0) D! -&gt; (20.0) C! -&gt; (10.0) E! = 60.0</CODE><BR><CODE>- : unit = ()</CODE><BR>

</PRE>
<BR>
<BR>

<H4> Performance Evaluation</H4>
We will test the performance of the functions <TT>dij</TT> and
<TT>dij_quick</TT> by iterating each one on a random list of sources.
In this way an application which frequently computes least
cost paths is simulated (for example a railway route planning system). <BR>
<BR>
We define the following function to time the calculations:


<PRE><BR># <B>let</B><CODE> </CODE>exe_time<CODE> </CODE>f<CODE> </CODE>g<CODE> </CODE>ss<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>t0<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Sys.time()<CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Printf.printf<CODE> </CODE><CODE>"Start (%5.2f)\n"</CODE><CODE> </CODE>t0;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>List.iter<CODE> </CODE><TT>(</TT><B>fun</B><CODE> </CODE>s<CODE> </CODE>-&gt;<CODE> </CODE>ignore<TT>(</TT>f<CODE> </CODE>s<CODE> </CODE>g<TT>)</TT><TT>)</TT><CODE> </CODE>ss;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>t1<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Sys.time()<CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Printf.printf<CODE> </CODE><CODE>"End (%5.2f)\n"</CODE><CODE> </CODE>t1;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Printf.printf<CODE> </CODE><CODE>"Duration = (%5.2f)\n"</CODE><CODE> </CODE><TT>(</TT>t1<CODE> </CODE><CODE>-.</CODE><CODE> </CODE>t0<TT>)</TT><CODE> </CODE>;;<BR><CODE>val exe_time : ('a -&gt; 'b -&gt; 'c) -&gt; 'b -&gt; 'a list -&gt; unit = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
We create a random list of 20000 nodes and measure the performance on the
graph <TT>a</TT>:


<PRE><BR># <B>let</B><CODE> </CODE>ss<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>ss0<CODE> </CODE><CODE>=</CODE><CODE> </CODE>ref<CODE> </CODE>[]<CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>i0<CODE> </CODE><CODE>=</CODE><CODE> </CODE>int_of_char<CODE> </CODE><CODE>'A'</CODE><CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>new_s<CODE> </CODE>i<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Char.escaped<CODE> </CODE><TT>(</TT>char_of_int<CODE> </CODE><TT>(</TT>i0<CODE>+</CODE>i<TT>)</TT><TT>)</TT><CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><B>for</B><CODE> </CODE>i<CODE>=</CODE><CODE>0</CODE><CODE> </CODE><B>to</B><CODE> </CODE><CODE>2</CODE><CODE>0</CODE><CODE>0</CODE><CODE>0</CODE><CODE>0</CODE><CODE> </CODE><B>do</B><CODE> </CODE>ss0<CODE> </CODE><CODE>:=</CODE><CODE> </CODE><TT>(</TT>new_s<CODE> </CODE><TT>(</TT>Random.int<CODE> </CODE>a<CODE>.</CODE>size<TT>)</TT><TT>)</TT><CODE>::!</CODE>ss0<CODE> </CODE><B>done</B>;<BR><CODE> </CODE><CODE> </CODE><CODE>!</CODE>ss0<CODE> </CODE>;;<BR><CODE>val ss : string list =</CODE><BR><CODE>  ["A"; "B"; "D"; "A"; "E"; "C"; "B"; "B"; "D"; "E"; "B"; "E"; "C"; "E"; "E";</CODE><BR><CODE>   "D"; "D"; "A"; "E"; ...]</CODE><BR># Printf.printf<CODE>"Function dij :\n"</CODE>;<BR><CODE> </CODE>exe_time<CODE> </CODE>dij<CODE> </CODE>a<CODE> </CODE>ss<CODE> </CODE>;;<BR><CODE>Function dij :</CODE><BR><CODE>Start ( 1.14)</CODE><BR><CODE>End ( 1.46)</CODE><BR><CODE>Duration = ( 0.32)</CODE><BR><CODE>- : unit = ()</CODE><BR># Printf.printf<CODE>"Function dij_quick :\n"</CODE>;<BR><CODE> </CODE>exe_time<CODE> </CODE>dij_quick<CODE> </CODE><TT>(</TT>create_comp_graph<CODE> </CODE>a<TT>)</TT><CODE> </CODE>ss<CODE> </CODE>;;<BR><CODE>Function dij_quick :</CODE><BR><CODE>Start ( 1.46)</CODE><BR><CODE>End ( 1.50)</CODE><BR><CODE>Duration = ( 0.04)</CODE><BR><CODE>- : unit = ()</CODE><BR>

</PRE>
<BR>
<BR>
The results confirm our assumption. The direct access to a result held in
the cache is considerably faster than a second computation of the result.<BR>
<BR>
<A NAME="toc177"></A>
<H3> A Graphical Interface</H3>
We use the <TT>Awi</TT> library to construct a graphical interface
to display graphs. The interface allows selection of the source
and destination nodes of the path. When the path is found, it is
displayed graphically. We define the type <I>'a gg</I>, containing
fields describing the graph and the computation, as well as fields of
the graphical interface.<BR>
<BR>


<PRE><BR># <CODE> </CODE>#load<CODE> </CODE><CODE>"PROGRAMMES/awi.cmo"</CODE>;;<BR>

</PRE>



<PRE><BR># <B>type</B><CODE> </CODE>'a<CODE> </CODE>gg<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE><B>mutable</B><CODE> </CODE>src<CODE> </CODE><CODE>:</CODE><CODE> </CODE>'a<CODE> </CODE><CODE>*</CODE><CODE> </CODE>Awi.component;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>mutable</B><CODE> </CODE>dest<CODE> </CODE><CODE>:</CODE><CODE> </CODE>'a<CODE> </CODE><CODE>*</CODE><CODE> </CODE>Awi.component;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>pos<CODE> </CODE><CODE>:</CODE><CODE> </CODE><TT>(</TT>int<CODE> </CODE><CODE>*</CODE><CODE> </CODE>int<TT>)</TT><CODE> </CODE>array;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>cg<CODE> </CODE><CODE>:</CODE><CODE> </CODE>'a<CODE> </CODE>comp_graph;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>mutable</B><CODE> </CODE>state<CODE> </CODE><CODE>:</CODE><CODE> </CODE>comp_state;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>mutable</B><CODE> </CODE>main<CODE> </CODE><CODE>:</CODE><CODE> </CODE>Awi.component;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>to_string<CODE> </CODE><CODE>:</CODE><CODE> </CODE>'a<CODE> </CODE>-&gt;<CODE> </CODE>string;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>from_string<CODE> </CODE><CODE>:</CODE><CODE> </CODE>string<CODE> </CODE>-&gt;<CODE> </CODE>'a<CODE> </CODE>}<CODE> </CODE>;;<BR>

</PRE>
<BR>
<BR>
The fields <TT>src</TT> and <TT>dest</TT> are tuples
(node, component), associating a node and a component. The field
<TT>pos</TT> contains the position of each component. The field
<TT>main</TT> is the main container of the set of components.
The two functions <TT>to_string</TT> and <TT>from_string</TT> are conversion
functions between type <I>'a</I> and strings. The elements necessary
to construct these values are the graph information, the position table and
the conversion functions.<BR>
<BR>


<PRE><BR># <B>let</B><CODE> </CODE>create_gg<CODE> </CODE>cg<CODE> </CODE>vpos<CODE> </CODE>ts<CODE> </CODE>fs<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE>{src<CODE> </CODE><CODE>=</CODE><CODE> </CODE>cg<CODE>.</CODE>g<CODE>.</CODE>nodes<CODE>.</CODE><TT>(</TT><CODE>0</CODE><TT>)</TT><CODE>,</CODE>Awi.empty_component;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>dest<CODE> </CODE><CODE>=</CODE><CODE> </CODE>cg<CODE>.</CODE>g<CODE>.</CODE>nodes<CODE>.</CODE><TT>(</TT><CODE>0</CODE><TT>)</TT><CODE>,</CODE>Awi.empty_component;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>pos<CODE> </CODE><CODE>=</CODE><CODE> </CODE>vpos;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>cg<CODE> </CODE><CODE>=</CODE><CODE> </CODE>cg;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>state<CODE> </CODE><CODE>=</CODE><CODE> </CODE>create_state<CODE> </CODE>()<CODE> </CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>main<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Awi.empty_component;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>to_string<CODE> </CODE><CODE>=</CODE><CODE> </CODE>ts;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>from_string<CODE> </CODE><CODE>=</CODE><CODE> </CODE>fs};;<BR><CODE>val create_gg :</CODE><BR><CODE>  'a comp_graph -&gt;</CODE><BR><CODE>  (int * int) array -&gt; ('a -&gt; string) -&gt; (string -&gt; 'a) -&gt; 'a gg = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>

<H4> Visualisation</H4>
In order to display the graph, the nodes have to be drawn, and the edges have
to be traced. The nodes are represented by button components of the
<TT>Awi</TT> library. The edges are traced directly in
the main window. The function <TT>display_edge</TT> displays the
edges. The function <TT>display_shortest_path</TT> displays the found path
in a different color.<BR>
<BR>

<H5> Drawing Edges</H5> 
An edge connects two nodes and has an associated weight.
The connection between two nodes can be represented by a line.
The main difficulty is indicating the orientation of the line.
We choose to represent it by an arrow. 
The arrow is rotated by the angle the line has with the
abscissa (the <I>x</I>-axis) to give it the proper orientation. Finally, the costs are displayed beside the edge.<BR>
<BR>
To draw the arrow of an edge we define the functions <TT>rotate</TT> and
<TT>translate</TT> which care respectively for rotation and shifting.
The function <TT>display_arrow</TT> draws the arrow.


<PRE><BR># <B>let</B><CODE> </CODE>rotate<CODE> </CODE>l<CODE> </CODE>a<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>ca<CODE> </CODE><CODE>=</CODE><CODE> </CODE>cos<CODE> </CODE>a<CODE> </CODE><CODE> </CODE><B>and</B><CODE> </CODE>sa<CODE> </CODE><CODE>=</CODE><CODE> </CODE>sin<CODE> </CODE>a<CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>List.map<CODE> </CODE><TT>(</TT><B>function</B><CODE> </CODE><TT>(</TT>x<CODE>,</CODE>y<TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE><TT>(</TT><CODE> </CODE>x<CODE>*.</CODE>ca<CODE> </CODE><CODE>+.</CODE><CODE> </CODE><CODE>-.</CODE>y<CODE>*.</CODE>sa<CODE>,</CODE><CODE> </CODE>x<CODE>*.</CODE>sa<CODE> </CODE><CODE>+.</CODE><CODE> </CODE>y<CODE>*.</CODE>ca<TT>)</TT><TT>)</TT><CODE> </CODE>l;;<BR><CODE>val rotate : (float * float) list -&gt; float -&gt; (float * float) list = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE>translate<CODE> </CODE>l<CODE> </CODE><TT>(</TT>tx<CODE>,</CODE>ty<TT>)</TT><CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE>List.map<CODE> </CODE><TT>(</TT><B>function</B><CODE> </CODE><TT>(</TT>x<CODE>,</CODE>y<TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE><TT>(</TT>x<CODE> </CODE><CODE>+.</CODE><CODE> </CODE>tx<CODE>,</CODE><CODE> </CODE>y<CODE> </CODE><CODE>+.</CODE><CODE> </CODE>ty<TT>)</TT><TT>)</TT><CODE> </CODE>l;;<BR><CODE>val translate :</CODE><BR><CODE>  (float * float) list -&gt; float * float -&gt; (float * float) list = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE>display_arrow<CODE> </CODE><TT>(</TT>mx<CODE>,</CODE>my<TT>)</TT><CODE> </CODE>a<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>triangle<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>[</CODE><TT>(</TT><CODE>5</CODE><CODE>.,</CODE><CODE>0</CODE><CODE>.</CODE><TT>)</TT>;<CODE> </CODE><TT>(</TT><CODE>-</CODE><CODE>3</CODE><CODE>.,</CODE><CODE>3</CODE><CODE>.</CODE><TT>)</TT>;<CODE> </CODE><TT>(</TT><CODE>1</CODE><CODE>.,</CODE><CODE>0</CODE><CODE>.</CODE><TT>)</TT>;<CODE> </CODE><TT>(</TT><CODE>-</CODE><CODE>3</CODE><CODE>.,-</CODE><CODE>3</CODE><CODE>.</CODE><TT>)</TT>;<CODE> </CODE><TT>(</TT><CODE>5</CODE><CODE>.,</CODE><CODE>0</CODE><CODE>.</CODE><TT>)</TT><CODE>]</CODE><CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>tr<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE> </CODE>rotate<CODE> </CODE>triangle<CODE> </CODE>a<CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>ttr<CODE> </CODE><CODE>=</CODE><CODE> </CODE>translate<CODE> </CODE>tr<CODE> </CODE><TT>(</TT>mx<CODE>,</CODE>my<TT>)</TT><CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>tt<CODE> </CODE><CODE>=</CODE><CODE> </CODE>List.map<CODE> </CODE><TT>(</TT><B>function</B><CODE> </CODE><TT>(</TT>x<CODE>,</CODE>y<TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE><TT>(</TT>int_of_float<CODE> </CODE>x<CODE>,</CODE><CODE> </CODE>int_of_float<CODE> </CODE>y<TT>)</TT><TT>)</TT><CODE> </CODE>ttr<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Graphics.fill_poly<CODE> </CODE><TT>(</TT>Array.of_list<CODE> </CODE>tt<TT>)</TT>;;<BR><CODE>val display_arrow : float * float -&gt; float -&gt; unit = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
The position of the text indicating the weight of an edge depends on the angle
of the edge.


<PRE><BR># <B>let</B><CODE> </CODE>display_label<CODE> </CODE><TT>(</TT>mx<CODE>,</CODE>my<TT>)</TT><CODE> </CODE>a<CODE> </CODE>lab<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE><TT>(</TT>sx<CODE>,</CODE>sy<TT>)</TT><CODE> </CODE><CODE>=</CODE><CODE> </CODE>Graphics.text_size<CODE> </CODE>lab<CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>pos<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>[</CODE><CODE> </CODE>float<TT>(</TT><CODE>-</CODE>sx<CODE>/</CODE><CODE>2</CODE><TT>)</TT><CODE>,</CODE>float<TT>(</TT><CODE>-</CODE>sy<TT>)</TT><CODE> </CODE><CODE>]</CODE><CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>pr<CODE> </CODE><CODE>=</CODE><CODE> </CODE>rotate<CODE> </CODE>pos<CODE> </CODE>a<CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>pt<CODE> </CODE><CODE>=</CODE><CODE> </CODE>translate<CODE> </CODE>pr<CODE> </CODE><TT>(</TT>mx<CODE>,</CODE>my<TT>)</TT><CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>px<CODE>,</CODE>py<CODE> </CODE><CODE>=</CODE><CODE> </CODE>List.hd<CODE> </CODE>pt<CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>ox<CODE>,</CODE>oy<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Graphics.current_point<CODE> </CODE>()<CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Graphics.moveto<CODE> </CODE><TT>(</TT><TT>(</TT>int_of_float<CODE> </CODE>mx<TT>)</TT><CODE>-</CODE>sx<CODE>-</CODE><CODE>6</CODE><TT>)</TT><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><TT>(</TT><TT>(</TT>int_of_float<CODE> </CODE>my<TT>)</TT><CODE> </CODE><TT>)</TT>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Graphics.draw_string<CODE> </CODE>lab;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Graphics.moveto<CODE> </CODE>ox<CODE> </CODE>oy;;<BR><CODE>val display_label : float * float -&gt; float -&gt; string -&gt; unit = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
The preceding functions are now used by the function <TT>display_edge</TT>.
Parameters are the graphical interface <TT>gg</TT>, the nodes <TT>i</TT>
and <TT>j</TT>, and the color (<TT>col</TT>) to use.


<PRE><BR># <B>let</B><CODE> </CODE>display_edge<CODE> </CODE>gg<CODE> </CODE>col<CODE> </CODE>i<CODE> </CODE>j<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>g<CODE> </CODE><CODE>=</CODE><CODE> </CODE>gg<CODE>.</CODE>cg<CODE>.</CODE>g<CODE> </CODE><B>in</B><CODE> </CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>x<CODE>,</CODE>y<CODE> </CODE><CODE>=</CODE><CODE> </CODE>gg<CODE>.</CODE>main<CODE>.</CODE>Awi.x<CODE>,</CODE>gg<CODE>.</CODE>main<CODE>.</CODE>Awi.y<CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>a_cost<CODE> </CODE>g<CODE>.</CODE>m<CODE>.</CODE><TT>(</TT>i<TT>)</TT><CODE>.</CODE><TT>(</TT>j<TT>)</TT><CODE> </CODE><B>then</B><CODE> </CODE><TT>(</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE><TT>(</TT>a1<CODE>,</CODE>b1<TT>)</TT><CODE> </CODE><CODE>=</CODE><CODE> </CODE>gg<CODE>.</CODE>pos<CODE>.</CODE><TT>(</TT>i<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>and</B><CODE> </CODE><TT>(</TT>a2<CODE>,</CODE>b2<TT>)</TT><CODE> </CODE><CODE>=</CODE><CODE> </CODE>gg<CODE>.</CODE>pos<CODE>.</CODE><TT>(</TT>j<TT>)</TT><CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>x0<CODE>,</CODE>y0<CODE> </CODE><CODE>=</CODE><CODE> </CODE>x<CODE>+</CODE>a1<CODE>,</CODE>y<CODE>+</CODE>b1<CODE> </CODE><CODE> </CODE><CODE> </CODE><B>and</B><CODE> </CODE>x1<CODE>,</CODE>y1<CODE> </CODE><CODE>=</CODE><CODE> </CODE>x<CODE>+</CODE>a2<CODE>,</CODE>y<CODE>+</CODE>b2<CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>rxm<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE> </CODE><TT>(</TT>float<TT>(</TT>x1<CODE>-</CODE>x0<TT>)</TT><TT>)</TT><CODE> </CODE><CODE>/.</CODE><CODE> </CODE><CODE>2</CODE><CODE>.</CODE><CODE> </CODE><CODE> </CODE><B>and</B><CODE> </CODE>rym<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE> </CODE><TT>(</TT>float<TT>(</TT>y1<CODE>-</CODE>y0<TT>)</TT><TT>)</TT><CODE> </CODE><CODE>/.</CODE><CODE> </CODE><CODE>2</CODE><CODE>.</CODE><CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>xm<CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT>float<CODE> </CODE>x0<TT>)</TT><CODE> </CODE><CODE>+.</CODE><CODE> </CODE>rxm<CODE> </CODE><B>and</B><CODE> </CODE>ym<CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT>float<CODE> </CODE>y0<TT>)</TT><CODE> </CODE><CODE>+.</CODE><CODE> </CODE>rym<CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Graphics.set_color<CODE> </CODE>col;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Graphics.moveto<CODE> </CODE>x0<CODE> </CODE>y0;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Graphics.lineto<CODE> </CODE>x1<CODE> </CODE>y1;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>a<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE> </CODE>atan2<CODE> </CODE>rym<CODE> </CODE>rxm<CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>display_arrow<CODE> </CODE><TT>(</TT>xm<CODE>,</CODE>ym<TT>)</TT><CODE> </CODE>a;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>display_label<CODE> </CODE><TT>(</TT>xm<CODE>,</CODE>ym<TT>)</TT><CODE> </CODE>a<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><TT>(</TT>string_of_float<TT>(</TT>float_of_cost<CODE> </CODE>g<CODE>.</CODE>m<CODE>.</CODE><TT>(</TT>i<TT>)</TT><CODE>.</CODE><TT>(</TT>j<TT>)</TT><TT>)</TT><TT>)</TT><TT>)</TT>;;<BR><CODE>val display_edge : 'a gg -&gt; Graphics.color -&gt; int -&gt; int -&gt; unit = &lt;fun&gt;</CODE><BR>

</PRE>

<BR>
<BR>

<H5> Displaying a Path</H5>
To display a path, all edges along the path are displayed. The graphical
display of a path towards a destination uses the same technique as
the textual display.


<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>display_shortest_path<CODE> </CODE>gg<CODE> </CODE>col<CODE> </CODE>dest<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>g<CODE> </CODE><CODE>=</CODE><CODE> </CODE>gg<CODE>.</CODE>cg<CODE>.</CODE>g<CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>belongs_to<CODE> </CODE>dest<CODE> </CODE>g<CODE> </CODE><B>then</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>d<CODE> </CODE><CODE>=</CODE><CODE> </CODE>index<CODE> </CODE>dest<CODE> </CODE>g<CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>aux<CODE> </CODE>is<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>is<CODE> </CODE><CODE>=</CODE><CODE> </CODE>gg<CODE>.</CODE>state<CODE>.</CODE>source<CODE> </CODE><B>then</B><CODE> </CODE>()<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE><TT>(</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>old<CODE> </CODE><CODE>=</CODE><CODE> </CODE>gg<CODE>.</CODE>state<CODE>.</CODE>paths<CODE>.</CODE><TT>(</TT>is<TT>)</TT><CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>display_edge<CODE> </CODE>gg<CODE> </CODE>col<CODE> </CODE>old<CODE> </CODE>is;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>aux<CODE> </CODE>old<CODE> </CODE><TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>not<TT>(</TT>a_cost<CODE> </CODE>gg<CODE>.</CODE>state<CODE>.</CODE>distances<CODE>.</CODE><TT>(</TT>d<TT>)</TT><TT>)</TT><CODE> </CODE><B>then</B><CODE> </CODE>Printf.printf<CODE> </CODE><CODE>"no way\n"</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE>aux<CODE> </CODE>d;;<BR><CODE>val display_shortest_path : 'a gg -&gt; Graphics.color -&gt; 'a -&gt; unit = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>

<H5> Displaying a Graph</H5>
The function <TT>display_gg</TT> displays a complete graph.
If the destination node is not empty, the path between the source and the
destination is traced.


<PRE><BR># <CODE> </CODE><B>let</B><CODE> </CODE>display_gg<CODE> </CODE>gg<CODE> </CODE>()<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE>Awi.display_rect<CODE> </CODE>gg<CODE>.</CODE>main<CODE> </CODE>();<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>for</B><CODE> </CODE>i<CODE>=</CODE><CODE>0</CODE><CODE> </CODE><B>to</B><CODE> </CODE>gg<CODE>.</CODE>cg<CODE>.</CODE>g<CODE>.</CODE>ind<CODE> </CODE><CODE>-</CODE><CODE>1</CODE><CODE> </CODE><B>do</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>for</B><CODE> </CODE>j<CODE>=</CODE><CODE>0</CODE><CODE> </CODE><B>to</B><CODE> </CODE>gg<CODE>.</CODE>cg<CODE>.</CODE>g<CODE>.</CODE>ind<CODE> </CODE><CODE>-</CODE><CODE>1</CODE><CODE> </CODE><B>do</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>i<CODE>&lt;&gt;</CODE><CODE> </CODE>j<CODE> </CODE><B>then</B><CODE> </CODE>display_edge<CODE> </CODE>gg<CODE> </CODE><TT>(</TT>Graphics.black<TT>)</TT><CODE> </CODE>i<CODE> </CODE>j<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>done</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>done</B>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>snd<CODE> </CODE>gg<CODE>.</CODE>dest<CODE> </CODE><CODE>!=</CODE><CODE> </CODE>Awi.empty_component<CODE> </CODE><B>then</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>display_shortest_path<CODE> </CODE>gg<CODE> </CODE>Graphics.red<CODE> </CODE><TT>(</TT>fst<CODE> </CODE>gg<CODE>.</CODE>dest<TT>)</TT>;;<BR><CODE>val display_gg : 'a gg -&gt; unit -&gt; unit = &lt;fun&gt;</CODE><BR>

</PRE>
 <BR>
<BR>

<H4> The Node Component</H4>The nodes still need to be drawn. Since the user is allowed to
choose the source and destination nodes, we define a component
for nodes.<BR>
<BR>
The user's main action is choosing the end nodes of the path
to be found. Thus a node must be a component that reacts to mouse clicks,
using its state to indicate if it has been chosen as a source or destination.
We choose the button component, which reacts to mouse clicks.<BR>
<BR>

<H5> Node Actions</H5>
It is necessary to indicate node selection. To show this, the
background color of a node is changed by the function <TT>inverse</TT>.


<PRE><BR># <B>let</B><CODE> </CODE>inverse<CODE> </CODE>b<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>gc<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Awi.get_gc<CODE> </CODE>b<CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>fcol<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Awi.get_gc_fcol<CODE> </CODE>gc<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>and</B><CODE> </CODE>bcol<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Awi.get_gc_bcol<CODE> </CODE>gc<CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Awi.set_gc_bcol<CODE> </CODE>gc<CODE> </CODE>fcol;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Awi.set_gc_fcol<CODE> </CODE>gc<CODE> </CODE>bcol;;<BR><CODE>val inverse : Awi.component -&gt; unit = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
The function <TT>action_click</TT> effects this selection. It is called when a
node is clicked on by the mouse. As parameters it takes the node associated
with the button and the graph to modify the source or the destination
of the search. When both nodes are selected, the function <TT>dij_quick</TT>
finds a least cost path.


<PRE>
<CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><BR># <B>let</B><CODE> </CODE>action_click<CODE> </CODE>node<CODE> </CODE>gg<CODE> </CODE>b<CODE> </CODE>bs<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE><TT>(</TT>s1<CODE>,</CODE>s<TT>)</TT><CODE> </CODE><CODE>=</CODE><CODE> </CODE>gg<CODE>.</CODE>src<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>and</B><CODE> </CODE><TT>(</TT>s2<CODE>,</CODE>d<TT>)</TT><CODE> </CODE><CODE>=</CODE><CODE> </CODE>gg<CODE>.</CODE>dest<CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE><CODE> </CODE>s<CODE> </CODE><CODE>==</CODE><CODE> </CODE>Awi.empty_component<CODE> </CODE><B>then</B><CODE> </CODE><TT>(</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>gg<CODE>.</CODE>src<CODE> </CODE><CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE><TT>(</TT>node<CODE>,</CODE>b<TT>)</TT>;<CODE> </CODE>inverse<CODE> </CODE>b<CODE> </CODE><TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>d<CODE> </CODE><CODE>==</CODE><CODE> </CODE>Awi.empty_component<CODE> </CODE><B>then</B><CODE> </CODE><TT>(</TT><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>inverse<CODE> </CODE>b;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>gg<CODE>.</CODE>dest<CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE><TT>(</TT>node<CODE>,</CODE>b<TT>)</TT>;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>gg<CODE>.</CODE>state<CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>dij_quick<CODE> </CODE>s1<CODE> </CODE>gg<CODE>.</CODE>cg;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>display_shortest_path<CODE> </CODE>gg<CODE> </CODE><TT>(</TT>Graphics.red<TT>)</TT><CODE> </CODE>node<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><TT>)</TT><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE><TT>(</TT>inverse<CODE> </CODE>s;<CODE> </CODE>inverse<CODE> </CODE>d;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>gg<CODE>.</CODE>dest<CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE><TT>(</TT>s2<CODE>,</CODE>Awi.empty_component<TT>)</TT>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>gg<CODE>.</CODE>src<CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>node<CODE>,</CODE>b;<CODE> </CODE>inverse<CODE> </CODE>b<TT>)</TT>;;<BR><CODE>val action_click : 'a -&gt; 'a gg -&gt; Awi.component -&gt; 'b -&gt; unit = &lt;fun&gt;</CODE><BR>

</PRE>
 <BR>
<BR>

<H5> Creating an Interface</H5>
The main function to create an interface takes an interface graph and a list
of options, creates the different components and associates them with the graph.
The parameters are the graph (<TT>gg</TT>), its dimensions (<TT>gw</TT> and
<TT>gh</TT>), a list of graph and node options (<TT>lopt</TT>) and a
list of node border options (<TT>lopt2</TT>).


<PRE>
<CODE> </CODE><CODE> </CODE><BR># <B>let</B><CODE> </CODE>main_gg<CODE> </CODE>gg<CODE> </CODE>gw<CODE> </CODE>gh<CODE> </CODE>lopt<CODE> </CODE>lopt2<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>gc<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Awi.make_default_context<CODE> </CODE>()<CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Awi.set_gc<CODE> </CODE>gc<CODE> </CODE>lopt;<CODE> </CODE><BR><CODE> </CODE><CODE>(* compute the maximal button size *)</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>vs<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Array.map<CODE> </CODE>gg<CODE>.</CODE>to_string<CODE> </CODE>gg<CODE>.</CODE>cg<CODE>.</CODE>g<CODE>.</CODE>nodes<CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>vsize<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Array.map<CODE> </CODE>Graphics.text_size<CODE> </CODE><CODE> </CODE>vs<CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>w<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Array.fold_right<CODE> </CODE><TT>(</TT><B>fun</B><CODE> </CODE><TT>(</TT>x<CODE>,</CODE>y<TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE>max<CODE> </CODE>x<TT>)</TT><CODE> </CODE><CODE> </CODE>vsize<CODE> </CODE><CODE>0</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>and</B><CODE> </CODE>h<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Array.fold_right<CODE> </CODE><TT>(</TT><B>fun</B><CODE> </CODE><TT>(</TT>x<CODE>,</CODE>y<TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE>max<CODE> </CODE>y<TT>)</TT><CODE> </CODE><CODE> </CODE>vsize<CODE> </CODE><CODE>0</CODE><CODE> </CODE><B>in</B><CODE> </CODE><CODE> </CODE><CODE> </CODE><BR><CODE> </CODE><CODE>(* create the main panel *)</CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>gg<CODE>.</CODE>main<CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>Awi.create_panel<CODE> </CODE><B>true</B><CODE> </CODE>gw<CODE> </CODE>gh<CODE> </CODE>lopt;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>gg<CODE>.</CODE>main<CODE>.</CODE>Awi.display<CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>display_gg<CODE> </CODE>gg;<BR><CODE> </CODE><CODE>(* create the buttons *)</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>vb_bs<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Array.map<CODE> </CODE><TT>(</TT><B>fun</B><CODE> </CODE>x<CODE> </CODE>-&gt;<CODE> </CODE>x<CODE>,</CODE>Awi.create_button<CODE> </CODE><TT>(</TT><CODE>" "</CODE><CODE>^</CODE><TT>(</TT>gg<CODE>.</CODE>to_string<CODE> </CODE>x<TT>)</TT><CODE>^</CODE><CODE>" "</CODE><TT>)</TT><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>lopt<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>gg<CODE>.</CODE>cg<CODE>.</CODE>g<CODE>.</CODE>nodes<CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>f_act_b<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Array.map<CODE> </CODE><TT>(</TT><B>fun</B><CODE> </CODE><TT>(</TT>x<CODE>,</CODE><TT>(</TT>b<CODE>,</CODE>bs<TT>)</TT><TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>ac<CODE> </CODE><CODE>=</CODE><CODE> </CODE>action_click<CODE> </CODE>x<CODE> </CODE><CODE> </CODE>gg<CODE> </CODE>b<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE>Awi.set_bs_action<CODE> </CODE>bs<CODE> </CODE>ac<TT>)</TT><CODE> </CODE><CODE> </CODE>vb_bs<CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>bb<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Array.map<CODE> </CODE><TT>(</TT><B>function</B><CODE> </CODE><TT>(</TT><CODE>_,</CODE><TT>(</TT>b<CODE>,_</CODE><TT>)</TT><TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE>Awi.create_border<CODE> </CODE>b<CODE> </CODE>lopt2<TT>)</TT><CODE> </CODE>vb_bs<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Array.iteri<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><TT>(</TT><B>fun</B><CODE> </CODE>i<CODE> </CODE><TT>(</TT>b<TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE><B>let</B><CODE> </CODE>x<CODE>,</CODE>y<CODE> </CODE><CODE>=</CODE><CODE> </CODE>gg<CODE>.</CODE>pos<CODE>.</CODE><TT>(</TT>i<TT>)</TT><CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Awi.add_component<CODE> </CODE>gg<CODE>.</CODE>main<CODE> </CODE><CODE> </CODE>b<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>[</CODE><CODE>"PosX"</CODE><CODE>,</CODE>Awi<CODE>.</CODE>Iopt<CODE> </CODE><TT>(</TT>x<CODE>-</CODE>w<CODE>/</CODE><CODE>2</CODE><TT>)</TT>;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>"PosY"</CODE><CODE>,</CODE><CODE> </CODE>Awi<CODE>.</CODE>Iopt<CODE> </CODE><TT>(</TT>y<CODE>-</CODE>h<CODE>/</CODE><CODE>2</CODE><TT>)</TT><CODE>]</CODE><TT>)</TT><CODE> </CODE>bb;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>();;<BR><CODE>val main_gg :</CODE><BR><CODE>  'a gg -&gt;</CODE><BR><CODE>  int -&gt;</CODE><BR><CODE>  int -&gt; (string * Awi.opt_val) list -&gt; (string * Awi.opt_val) list -&gt; unit =</CODE><BR><CODE>  &lt;fun&gt;</CODE><BR>

</PRE>

The buttons are created automatically. They are positioned on the main window.<BR>
<BR>

<H5> Testing the Interface</H5>
Everything is ready to create an interface now. We use a graph whose
nodes are character strings to simplify the conversion functions.
We construct the graph <TT>gg</TT> as follows:


<PRE><BR># <B>let</B><CODE> </CODE>id<CODE> </CODE>x<CODE> </CODE><CODE>=</CODE><CODE> </CODE>x;;<BR># <B>let</B><CODE> </CODE>pos<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE> </CODE><CODE>[|</CODE><CODE> </CODE><CODE>2</CODE><CODE>0</CODE><CODE>0</CODE><CODE>,</CODE><CODE> </CODE><CODE>3</CODE><CODE>0</CODE><CODE>0</CODE>;<CODE> </CODE><CODE>8</CODE><CODE>0</CODE><CODE>,</CODE><CODE> </CODE><CODE>2</CODE><CODE>0</CODE><CODE>0</CODE><CODE> </CODE>;<CODE> </CODE><CODE>1</CODE><CODE>0</CODE><CODE>0</CODE><CODE>,</CODE><CODE> </CODE><CODE>1</CODE><CODE>0</CODE><CODE>0</CODE>;<CODE> </CODE><CODE>2</CODE><CODE>0</CODE><CODE>0</CODE><CODE>,</CODE><CODE> </CODE><CODE>1</CODE><CODE>0</CODE><CODE>0</CODE>;<CODE> </CODE><CODE> </CODE><CODE>2</CODE><CODE>6</CODE><CODE>0</CODE><CODE>,</CODE><CODE> </CODE><CODE>2</CODE><CODE>0</CODE><CODE>0</CODE><CODE> </CODE><CODE>|]</CODE>;;<CODE> </CODE><BR># <B>let</B><CODE> </CODE>gg<CODE> </CODE><CODE>=</CODE><CODE> </CODE>create_gg<CODE> </CODE><CODE> </CODE><TT>(</TT>create_comp_graph<CODE> </CODE><TT>(</TT>test_aho()<TT>)</TT><TT>)</TT><CODE> </CODE>pos<CODE> </CODE>id<CODE> </CODE>id;;<BR># main_gg<CODE> </CODE><CODE> </CODE>gg<CODE> </CODE><CODE>4</CODE><CODE>0</CODE><CODE>0</CODE><CODE> </CODE><CODE>4</CODE><CODE>0</CODE><CODE>0</CODE><CODE> </CODE><CODE>[</CODE><CODE>"Background"</CODE><CODE>,</CODE><CODE> </CODE>Awi<CODE>.</CODE>Copt<CODE> </CODE><CODE> </CODE><TT>(</TT>Graphics.rgb<CODE> </CODE><CODE>1</CODE><CODE>3</CODE><CODE>0</CODE><CODE> </CODE><CODE>1</CODE><CODE>3</CODE><CODE>0</CODE><CODE> </CODE><CODE>1</CODE><CODE>3</CODE><CODE>0</CODE><TT>)</TT>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>"Foreground"</CODE><CODE>,</CODE>Awi<CODE>.</CODE>Copt<CODE> </CODE><CODE> </CODE>Graphics.green<CODE>]</CODE><CODE> </CODE><BR><CODE> </CODE><CODE>[</CODE><CODE> </CODE><CODE>"Relief"</CODE><CODE>,</CODE><CODE> </CODE>Awi<CODE>.</CODE>Sopt<CODE> </CODE><CODE>"Top"</CODE>;<CODE>"Border_size"</CODE><CODE>,</CODE><CODE> </CODE>Awi<CODE>.</CODE>Iopt<CODE> </CODE><CODE>2</CODE><CODE>]</CODE>;;<BR>

</PRE>
<BR>
<BR>
Calling <EM>Awi.loop true false gg.main;;</EM> starts the interaction loop of
the <TT>Awi</TT> library.<BR>
<BR>
<BLOCKQUOTE><DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV>
<DIV ALIGN=center>
<IMG SRC="book-ora056.gif">
</DIV>
<BR>
<DIV ALIGN=center>Figure 13.9: Selecting the nodes for a search</DIV><BR>

<A NAME="fig-ahointer"></A>
<DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>Figure <A HREF="book-ora125.html#fig-ahointer">13.9</A> shows the computed path between the nodes
<TT>"A"</TT> and <TT>"E"</TT>. The edges on the path have changed their color.
<BR>
<BR>
<A NAME="toc178"></A>
<H3> Creating a Standalone Application</H3>
We will now show the steps needed to construct a standalone
application. The application takes
the name of a file describing the graph as an argument.
For standalone applications, it is not necesary to have an
Objective CAML distribution on the execution machine.<BR>
<BR>

<H4> A Graph Description File</H4>
The file containes information about the graph as well as information
used for the graphical interface. For the latter information, we define
a second format. From this graphical description, we construct a value
of the type <I>g_info</I>.


<PRE><BR># <B>type</B><CODE> </CODE>g_info<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{npos<CODE> </CODE><CODE>:</CODE><CODE> </CODE><TT>(</TT>int<CODE> </CODE><CODE>*</CODE><CODE> </CODE>int<TT>)</TT><CODE> </CODE>array;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>mutable</B><CODE> </CODE>opt<CODE> </CODE><CODE>:</CODE><CODE> </CODE>Awi.lopt;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>mutable</B><CODE> </CODE>g_w<CODE> </CODE><CODE>:</CODE><CODE> </CODE>int;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>mutable</B><CODE> </CODE>g_h<CODE> </CODE><CODE>:</CODE><CODE> </CODE>int};;<BR>

</PRE>
<BR>
<BR>
The format for the graphical information is described by the four key words
of list <TT>key2</TT>. 


<PRE><BR># <B>let</B><CODE> </CODE>key2<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>[</CODE><CODE>"HEIGHT"</CODE>;<CODE> </CODE><CODE>"LENGTH"</CODE>;<CODE> </CODE><CODE>"POSITION"</CODE>;<CODE> </CODE><CODE>"COLOR"</CODE><CODE>]</CODE>;;<BR><CODE>val key2 : string list = ["HEIGHT"; "LENGTH"; "POSITION"; "COLOR"]</CODE><BR># <B>let</B><CODE> </CODE>lex2<CODE> </CODE>l<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Genlex.make_lexer<CODE> </CODE>key2<CODE> </CODE><TT>(</TT>Stream.of_string<CODE> </CODE>l<TT>)</TT>;;<BR><CODE>val lex2 : string -&gt; Genlex.token Stream.t = &lt;fun&gt;</CODE><BR><BR># <B>let</B><CODE> </CODE>pars2<CODE> </CODE>g<CODE> </CODE>gi<CODE> </CODE>s<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>s<CODE> </CODE><B>with</B><CODE> </CODE><B>parser</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>[&lt;</CODE><CODE> </CODE><CODE>'</CODE><TT>(</TT>Genlex<CODE>.</CODE>Kwd<CODE> </CODE><CODE>"HEIGHT"</CODE><TT>)</TT>;<CODE> </CODE><CODE>'</CODE><TT>(</TT>Genlex<CODE>.</CODE>Int<CODE> </CODE>i<TT>)</TT><CODE> </CODE><CODE>&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE>gi<CODE>.</CODE>g_h<CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>i<BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE> </CODE><CODE>[&lt;</CODE><CODE> </CODE><CODE>'</CODE><TT>(</TT>Genlex<CODE>.</CODE>Kwd<CODE> </CODE><CODE>"LENGTH"</CODE><TT>)</TT>;<CODE> </CODE><CODE>'</CODE><TT>(</TT>Genlex<CODE>.</CODE>Int<CODE> </CODE>i<TT>)</TT><CODE> </CODE><CODE>&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE>gi<CODE>.</CODE>g_w<CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>i<BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE> </CODE><CODE>[&lt;</CODE><CODE> </CODE><CODE>'</CODE><TT>(</TT>Genlex<CODE>.</CODE>Kwd<CODE> </CODE><CODE>"POSITION"</CODE><TT>)</TT>;<CODE> </CODE><CODE>'</CODE><TT>(</TT>Genlex<CODE>.</CODE>Ident<CODE> </CODE>s<TT>)</TT>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>'</CODE><TT>(</TT>Genlex<CODE>.</CODE>Int<CODE> </CODE>i<TT>)</TT>;<CODE> </CODE><CODE>'</CODE><TT>(</TT>Genlex<CODE>.</CODE>Int<CODE> </CODE>j<TT>)</TT><CODE> </CODE><CODE>&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE>gi<CODE>.</CODE>npos<CODE>.</CODE><TT>(</TT>index<CODE> </CODE>s<CODE> </CODE>g<TT>)</TT><CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE><TT>(</TT>i<CODE>,</CODE>j<TT>)</TT><BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE> </CODE><CODE>[&lt;</CODE><CODE> </CODE><CODE>'</CODE><TT>(</TT>Genlex<CODE>.</CODE>Kwd<CODE> </CODE><CODE>"COLOR"</CODE><TT>)</TT>;<CODE> </CODE><CODE>'</CODE><TT>(</TT>Genlex<CODE>.</CODE>Ident<CODE> </CODE>s<TT>)</TT>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>'</CODE><TT>(</TT>Genlex<CODE>.</CODE>Int<CODE> </CODE>r<TT>)</TT>;<CODE> </CODE><CODE>'</CODE><TT>(</TT>Genlex<CODE>.</CODE>Int<CODE> </CODE>g<TT>)</TT>;<CODE> </CODE><CODE>'</CODE><TT>(</TT>Genlex<CODE>.</CODE>Int<CODE> </CODE>b<TT>)</TT><CODE> </CODE><CODE>&gt;]</CODE><CODE> </CODE>-&gt;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>gi<CODE>.</CODE>opt<CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE><TT>(</TT>s<CODE>,</CODE><CODE> </CODE>Awi<CODE>.</CODE>Copt<CODE> </CODE><TT>(</TT>Graphics.rgb<CODE> </CODE>r<CODE> </CODE>g<CODE> </CODE>b<TT>)</TT><TT>)</TT>::gi<CODE>.</CODE>opt<BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>[&lt;&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE>();;<BR><CODE>val pars2 : string graph -&gt; g_info -&gt; Genlex.token Stream.t -&gt; unit = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>

<H4> Creating the Application</H4>
The function <TT>create_graph</TT> takes the name of a file as input
and returns a couple composed of a graph and associated graphical
information.


<PRE><BR># <B>let</B><CODE> </CODE>create_gg_graph<CODE> </CODE>name<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>g<CODE> </CODE><CODE>=</CODE><CODE> </CODE>create_graph<CODE> </CODE>name<CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>gi<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{npos<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Array.create<CODE> </CODE>g<CODE>.</CODE>size<CODE> </CODE><TT>(</TT><CODE>0</CODE><CODE>,</CODE><CODE>0</CODE><TT>)</TT>;<CODE> </CODE>opt<CODE>=[]</CODE>;<CODE> </CODE>g_w<CODE> </CODE><CODE>=</CODE><CODE>0</CODE>;<CODE> </CODE>g_h<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>0</CODE>;}<CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>ic<CODE> </CODE><CODE>=</CODE><CODE> </CODE>open_in<CODE> </CODE>name<CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>try</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>print_string<CODE> </CODE><TT>(</TT><CODE>"Loading (pass 2) "</CODE><CODE> </CODE><CODE>^</CODE>name<CODE> </CODE><CODE>^</CODE><CODE>" : "</CODE><TT>)</TT>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>while</B><CODE> </CODE><B>true</B><CODE> </CODE><B>do</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>print_string<CODE> </CODE><CODE>"."</CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>l<CODE> </CODE><CODE>=</CODE><CODE> </CODE>input_line<CODE> </CODE>ic<CODE> </CODE><B>in</B><CODE> </CODE>pars2<CODE> </CODE>g<CODE> </CODE>gi<CODE> </CODE><TT>(</TT>lex2<CODE> </CODE>l<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>done</B><CODE> </CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>g<CODE>,</CODE>gi<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>with</B><CODE> </CODE>End_of_file<CODE> </CODE>-&gt;<CODE> </CODE>print_newline();<CODE> </CODE>close_in<CODE> </CODE>ic;<CODE> </CODE>g<CODE>,</CODE>gi;;<BR><CODE>val create_gg_graph : string -&gt; string graph * g_info = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
The function <TT>create_app</TT> constructs the interface of a graph.


<PRE><BR># <B>let</B><CODE> </CODE>create_app<CODE> </CODE>name<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>g<CODE>,</CODE>gi<CODE> </CODE><CODE>=</CODE><CODE> </CODE>create_gg_graph<CODE> </CODE>name<CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>size<CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT>string_of_int<CODE> </CODE>gi<CODE>.</CODE>g_w<TT>)</TT><CODE> </CODE><CODE>^</CODE><CODE> </CODE><CODE>"x"</CODE><CODE> </CODE><CODE>^</CODE><CODE> </CODE><TT>(</TT>string_of_int<CODE> </CODE>gi<CODE>.</CODE>g_h<TT>)</TT><CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE>Graphics.open_graph<CODE> </CODE><TT>(</TT><CODE>" "</CODE><CODE>^</CODE>size<TT>)</TT>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>gg<CODE> </CODE><CODE>=</CODE><CODE> </CODE>create_gg<CODE> </CODE><TT>(</TT>create_comp_graph<CODE> </CODE>g<TT>)</TT><CODE> </CODE>gi<CODE>.</CODE>npos<CODE> </CODE>id<CODE> </CODE>id<CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE>main_gg<CODE> </CODE>gg<CODE> </CODE>gi<CODE>.</CODE>g_w<CODE> </CODE>gi<CODE>.</CODE>g_h<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>[</CODE><CODE> </CODE><CODE>"Background"</CODE><CODE>,</CODE><CODE> </CODE>Awi<CODE>.</CODE>Copt<CODE> </CODE><TT>(</TT>Graphics.rgb<CODE> </CODE><CODE>1</CODE><CODE>3</CODE><CODE>0</CODE><CODE> </CODE><CODE>1</CODE><CODE>3</CODE><CODE>0</CODE><CODE> </CODE><CODE>1</CODE><CODE>3</CODE><CODE>0</CODE><TT>)</TT><CODE> </CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>"Foreground"</CODE><CODE>,</CODE><CODE> </CODE>Awi<CODE>.</CODE>Copt<CODE> </CODE>Graphics.green<CODE> </CODE><CODE>]</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>[</CODE><CODE> </CODE><CODE>"Relief"</CODE><CODE>,</CODE><CODE> </CODE>Awi<CODE>.</CODE>Sopt<CODE> </CODE><CODE>"Top"</CODE><CODE> </CODE>;<CODE> </CODE><CODE>"Border_size"</CODE><CODE>,</CODE><CODE> </CODE>Awi<CODE>.</CODE>Iopt<CODE> </CODE><CODE>2</CODE><CODE> </CODE><CODE>]</CODE><CODE> </CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE>gg;;<BR><CODE>val create_app : string -&gt; string gg = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
Finally, the function <TT>main</TT> takes the name of the file from the
command line, constructs a graph with an interface and starts the interaction
loop on the main component of the graph interface.


<PRE><BR># <B>let</B><CODE> </CODE>main<CODE> </CODE>()<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE><TT>(</TT>Array.length<CODE> </CODE>Sys.argv<CODE> </CODE><TT>)</TT><CODE> </CODE><CODE>&lt;&gt;</CODE><CODE> </CODE><CODE>2</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>then</B><CODE> </CODE>Printf.printf<CODE> </CODE><CODE>"Usage: dij.exe filename\n"</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>gg<CODE> </CODE><CODE>=</CODE><CODE> </CODE>create_app<CODE> </CODE>Sys.argv<CODE>.</CODE><TT>(</TT><CODE>1</CODE><TT>)</TT><CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Awi.loop<CODE> </CODE><B>true</B><CODE> </CODE><B>false</B><CODE> </CODE>gg<CODE>.</CODE>main;;<BR><CODE>val main : unit -&gt; unit = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
The last expression of that program starts the function <TT>main</TT>.<BR>
<BR>

<H4> The Executable</H4>
The motivation for making a standalone application is to support its
distribution. We collect the types and functions described in this section
in the file <TT>dij.ml</TT>. Then we compile the file, adding the different
libraries which are used. Here is the command to compile it under Linux.
<PRE>
ocamlc -custom -o dij.exe graphics.cma awi.cmo graphs.ml \
    -cclib -lgraphics -cclib -L/usr/X11/lib -cclib -lX11
</PRE>Compiling standalone applications using the <TT>Graphics</TT> library
is described in chapters <A HREF="index.html#chap-PG">5</A> and <A HREF="index.html#chap-Compilation">7</A>. <BR>
<BR>
<A NAME="toc179"></A>
<H3> Final Notes</H3>
The skeleton of this application is sufficiently general to be used in
contexts other than the search for traveling paths. Different types of
problems can be represented by a weighted graph. For example the search for
a path in a labyrinth can be coded in a graph where each intersection is a
node. Finding a solution corresponds to computing the shortest path between
the start and the goal.<BR>
<BR>
To compare the performance betwen C and Objective CAML, we wrote Dijkstra's
algorithm in C. The C program uses the Objective CAML data structures to perform
the calculations.<BR>
<BR>
To improve the graphical interface, we add a <I>textfield</I>
for the name of the file and two buttons to load and to store a graph.
The user may then modify the positions of the nodes by mouse to improve
the appearance.<BR>
<BR>
A second improvement of the graphical interface is the ability to choose
the form of the nodes. To display a button, a function tracing a rectangle
is called. The display functions can be specialized to use polygons for
nodes.<BR>
<BR>


<BR>
<BR>
<BR>
<BR>
<HR>
<A HREF="book-ora124.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="index.html"><IMG SRC ="contents_motif.gif" ALT="Contents"></A>
<A HREF="book-ora127.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
